#pragma once
#include <iostream>
#include <vector>

namespace nhydata
{
template<class K>
class HashFunc
{
public:
    size_t operator()(const K& key){
        return key;
    }
};

template<>
class HashFunc<std::string>
{
public:
    size_t operator()(const std::string& str){
        size_t hash = 0;
        for(auto c : str){
            hash += c;
            hash *= 31;
        }
        return hash;
    }
};



namespace open_address
{
    enum States
    {
        EXIST,DELETE,EMPTY
    };

    template<class K,class V>
    struct HashData
    {
        std::pair<K,V> kv_;
        States st_ = EMPTY;
    };

    template<class K,class V>
    class HashTable
    {
    public:
        bool insert(const std::pair<K,V>& kv){
            if(find(kv.first)) return false;
                
            //扩容
            if(tables_.size() == 0 || n_*10 / tables_.size() > 7){
                size_t newsize = tables_.size() == 0 ? 10 : 2*tables_.size();
                HashTable<K,V> newht;
                newht.tables_.resize(newsize);
                for(const HashData<K,V>& data : tables_){
                    if(data.st_ == EXIST){
                        newht.insert(data.kv_);
                    }
                }
                tables_.swap(newht.tables_);
            }
            size_t hashi = kv.first % tables_.size();
            size_t index = hashi;


            while(tables_[index].st_ == EXIST){
                index = (index++)%tables_.size();
            }
            tables_[index].kv_ = kv;
            tables_[index].st_ = EXIST;
            n_ ++;

            return true;
        }

        HashData<K,V>* find(const K& k){
            if(tables_.size() == 0) return nullptr;
            size_t hashi = k % tables_.size();
            size_t index = hashi;
            while(tables_[index].st_ != EMPTY){

                if(tables_[index].st_ == EXIST && tables_[index].kv_.first == k){
                    return &(tables_[index]);
                }
                index++;
                index%=tables_.size();
                if(index == hashi) return nullptr;
            }
            return nullptr;
        }

        bool erase(const K& k){
            HashData<K,V>* ret = find(k);
            if(ret){
                ret->st_ = DELETE;
                n_ --;
                return true;
            }
            return false;
        }

    private:
        std::vector<HashData<K,V>> tables_;
        size_t n_ = 0;
    };


}// namespace open_address end

namespace zipper
{   
    template<class K,class V>
    struct HashNode
    {
        HashNode(const std::pair<K,V>& kv)
            :kv_(kv) , nx_(nullptr)
        {

        }
        std::pair<K,V> kv_;
        HashNode<K,V>* nx_;
    };

    template<class K,class V,class Hash>
    class HashTable
    {
    public:
        using Node = HashNode<K,V>;
        HashTable(){}

        bool insert(const std::pair<K,V>& kv){
            if(find(kv.first)) return false;
            Hash getHash;
            //扩容
            if(n_ == tables_.size()){
                size_t newsize = GetNextPrime(tables_.size());
                std::vector<Node*> newtables_(newsize,nullptr);
                for(Node* & node: tables_){
                    while(node){
                        Node* next = node->nx_;
                        size_t hashi = getHash(node->kv_.first) % newtables_.size();
                        node->nx_ = newtables_[hashi];
                        newtables_[hashi] = node;
                        node = next;
                    }
                }
                tables_.swap(newtables_);
            }
            //insert
            size_t hashi = getHash(kv.first) % tables_.size();
            Node* newnode = new Node(kv);
            newnode->nx_ = tables_[hashi];
            tables_[hashi]=newnode;
            n_++;
            return true;
        }   

        Node* find(const K& key){
            if(tables_.size() == 0) return nullptr;
            Hash getHash;
            size_t hashi = getHash(key) % tables_.size();
            Node* cur = tables_[hashi];
            while(cur){
                if(cur->kv_.first == key){
                    return cur;
                }
                cur = cur->nx_;
            }
            return nullptr;
        }

        bool erase(const K& key){
            Node* ret = find(key);
            if(ret == nullptr) return false;
            Hash getHash;
            size_t hashi = getHash(key)%tables_.size();
            Node* cur = tables_[hashi];
            if(ret == cur){
                tables_[hashi] = ret->nx_;
            } else {
                while(cur->nx_ != ret){
                    cur = cur->nx_;
                }
                cur->nx_ = ret->nx_;
            }
            delete ret;
            n_--;
            return true;
        }
    private:
        size_t GetNextPrime(size_t prime)
		{
			// SGI
			static const int __stl_num_primes = 28;
			static const unsigned long __stl_prime_list[__stl_num_primes] ={
				53, 97, 193, 389, 769,
				1543, 3079, 6151, 12289, 24593,
				49157, 98317, 196613, 393241, 786433,
				1572869, 3145739, 6291469, 12582917, 25165843,
				50331653, 100663319, 201326611, 402653189, 805306457,
				1610612741, 3221225473, 4294967291
			};
			size_t i = 0;
			for (; i < __stl_num_primes; ++i){
				if (__stl_prime_list[i] > prime) return __stl_prime_list[i];
			}
			return __stl_prime_list[i];
		}
    private:
        std::vector<Node*> tables_;
        size_t n_ = 0;
    }; 
}//namespace zipper end

}// namespace nhydata end